package 数组;


import java.util.HashSet;

/**
 * 给定一个含有 n 个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，
 * 并返回其长度。如果不存在符合条件的子数组，返回 0 。
 * User: zhaixiaolong Date:2024/1/29 16:53 ProjectName: algorithm Version:
 */
public class 滑动窗口 {

    public static void main(String[] args) {

    }

    public static int minLength(int[] nums, int target) {
        int minLength = 0;
        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            int n = 1;
            for (int endIndex = i + 1; endIndex < nums.length; endIndex++) {
                sum += nums[endIndex];
                n++;
                if (sum == target && (minLength == 0 || minLength > n)) {
                    minLength = n;
                }
            }
        }
        return minLength;
    }


    /**
     * 滑动窗口
     *
     * @param nums
     * @param target
     * @return
     */
    public static int minLength2(int[] nums, int target) {
        int minLength = Integer.MAX_VALUE;
        int startIndex = 0, endIndex = 0;
        int sum = 0;
        while (endIndex < nums.length) {
            // sum累加，end右移
            sum += nums[endIndex++];
            while (sum >= target && startIndex < endIndex) {
                minLength = Math.min(minLength, endIndex - startIndex);
                // 移动start
                sum -= nums[startIndex++];
            }
        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }


    /**
     * 滑动窗口
     *
     * @param nums
     * @param target
     * @return
     */
    public static int minLength3(int[] nums, int target) {
        int startIndex = 0, endIndex = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;
        while (endIndex < nums.length) {
            // 窗口扩大;尾指针移动
            sum += nums[endIndex++];
            while (sum >= target && startIndex < endIndex) {
                // 窗口缩小
                // 计算当前窗口长度；判断最小长度
                minLength = Math.min(minLength, endIndex - startIndex);
                sum -= nums[startIndex++];
            }
        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;

    }


    /**
     * 12345
     *
     * @param nums
     * @param k
     * @return
     */
    public static Boolean findRepeat(int[] nums, int k) {
        HashSet<Integer> set = new HashSet<>(k);
        for (int i = 0; i < nums.length; i++) {
            if (set.contains(nums[i])) {
                return Boolean.TRUE;
            }
            set.add(k);
            if (set.size() > k) {
                set.remove(nums[i - k]);
            }
        }
        return Boolean.FALSE;
    }
}
